1/1 | 2/1 | 3/1 | 4/1 | 5/1 | 6/1 | ... |
1/2 | 2/2 | 3/2 | 4/2 | 5/2 | 6/2 | ... |
1/3 | 2/3 | 3/3 | 4/3 | 5/3 | 6/3 | ... |
1/4 | 2/4 | 3/4 | 4/4 | 5/4 | 6/4 | ... |
1/5 | 2/5 | 3/5 | 4/5 | 5/5 | 6/5 | ... |
1/6 | 2/6 | 3/6 | 4/6 | 5/6 | 6/6 | ... |
... | ... | ... | ... | ... | ... | ... |
0, 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, ...
Definition 1. An algebraic number is the solution to a
polynomial equation with integer coefficients.
Fact 2. A polynomial equation of degree N can have at
most N distinct real number solutions.
Fact 3. There are a finite number of integer polynomial
equations of degree N where the sum of the absolute values of the coefficients
is less than a given number K.
Proof Procedure: (modified
slightly from Cantor's)
First:
List algebraic number roots from integer polynomials
of degree 1 with sum of the absolute values of the coefficients equal to
1. (This is just 1x=0 and -1x=0.)
Then:
use degree 1, sum 2;
(This is 2x=0, -2x=0, 1+1x=0, -1+1x=0, 1-1x=0, -1-1x=0.)
then degree 2, sum 1;
then degree 3, sum 1;
then degree 2, sum 2;
then degree 1, sum 3;. ...
Consider a sequence of integers, with each integer between
0 and 9.
If we let kth integer of the sequence determine the 2k+1
th decimal place of a number then we can determine a unique real number
by specifying that the 2k th decimal be a 5.
Let S be the set of of all real numbers that are specified
in this fashion.
S is a subset of [0,1].
Suppose there is a function, f : N
-> S.
Then let b=.b1 5 b3 5 b5 5 b7 5 b9 5 ... where we choose
b2k+1 so that it is not equal to the 2k+1st digit of f(k).
Thus b is a member of s but b not equal to f(k) for any
k, so f is not "onto".
Hence S is not a countable set, and consequently neither
is [0,1].
Note: The set of {0,1} - valued sequences is also
"uncountable."
Proof: Suppose f: R -> P(R).
Let B = {x such that x is not an element of f(x)}.
Suppose B = f(b) for some b.
If b is in B then b is not in f(b)=B, which is a contradiction.
So b is not in B, but then b is not in f(b), so b is
in B!
Thus B is not f(b) for any b, and f is not onto.
Thus: There are sets which are larger
than the reals.
Footnote on measuring sets of real numbers:
The rational numbers between
0 and 1 have "measure" zero.
Proof: List the rationals
a1,a2,a3,... and for any number
s, use an interval of length s/2k about ak.
Then the set of rational numbers has measure less than s. Since s can be
any number, the set of rationals between 0 and 1 has measure 0.
Generalization: Any countable set of real numbers
has "measure" zero.